1. Field of the Invention
The present invention is related to using multi-hop wireless networks to provide network access services, and, to a particular security scheme for a multi-hop wireless access network.
2. Description of the Related Art
The IEEE 802.11 standard (“Part 11: Wireless LAN Medium Access Control (MAC) and physical layer specifications”, IEEE, 1999, and including all variations) is known in the art. In the current 802.11 WLAN architecture, mobile clients connect wirelessly to Access Points (APs) to acquire connectivity to a backbone network to which the APs are attached. The backbone network is typically wired and is then connected to the rest of the organizational network.
The WLAN architecture is ideal for network administrators who wish to wirelessly extend the boundary of their existing wired campus or corporate networks and to provide campus-wide mobility support. Under this architecture, mobile clients are no longer constrained by network cables and wall jacks as long as they maintain direct wireless contacts with some AR. Due to a number of dynamic configuration protocols such as the DHCP, mobile clients can easily join the WLAN with little or no user configuration effort. A user can move freely within the coverage area of the APs. When the user moves across the boundaries of the service areas of APs, WLAN and bridge protocols can update the link layer connectivity for the user so that on going communication sessions are not interrupted by the handoff and actual communication carrier (radio frequency) switch.
While mobile clients can enjoy the convenience of wireless network connectivity, on the other hand, it is not a trivial task to deploy a WLAN. APs need to be interconnected via a backbone network, typically a wired LAN. Therefore network cables must be installed to connect the APs to the existing network infrastructure. Electrical wires must also be in place to supply operating power to the APs. In addition, in order to determine the locations for the APs, WLAN planners need to predict wireless usage and conduct site surveys to determine the radio propagation characteristics. Operating channels also need to be allocated to each AP to keep the interference between neighboring communication cells to a minimum. After the deployment, it becomes another costly task to change the placement of the APs since the cables and wires need to be changed as well. If the usage pattern changes, oftentimes the WLAN is not able to be dynamically reconfigured to adapt to the changes.
Another problem with the existing IEEE 802.11 WLAN lies in its current security mechanism. In a WLAN, all transmitted bits are delivered over the air, which is an open communication medium to which anyone has access if he/she is within the radio signal range and has a radio device capable of receiving WLAN radio signals. Thus, encryption must be applied to sensitive data so that only the intended recipients can reconstruct and comprehend the data.
The IEEE 802.11 standard relies on the Wired Equivalency Privacy (WEP) protocol for its data protection. WEP uses a shared secret key of 40 bits (or 104 bits in a later version). A 24 bit Initial Vector (IV) is concatenated with the shared key to create a 64 bit (or 128 bit in the later standard) seed. The seed is then fed to a RC4 Pseudo Random Number Generator (PRNG) to generate a random bit sequence, which is used as the frame encryption key stream. The IV may be changed for every data frame encrypted so that the seed for the RC4 PRNG is different for every data frame. Thus, a different key stream is generated for encrypting each data frame. The IV is enclosed as clear text in each data frame so that the receiver may concatenate the received IV with the shared secret key to produce the RC4 PRNG seed and compute the decryption key stream. However, due to the limited IV size, there are only 2^24, about 16 million, distinct key streams. Given the size of an average data frame and the transmission rate supported by IEEE 802.11, a busy AP may exhaust the distinct key stream space very quickly and be forced to reuse the encryption key stream. Since the IVs are enclosed as clear text in each data frame, it is relatively easy for an attacker to recognize a reused key stream. The attacker may collect pieces of cipher text that are encrypted with the same key stream and perform statistical analysis to attack and recover the plaintext. An attacker may also build up a dictionary of all possible key streams. In addition to vulnerabilities to these types of attacks, the security research community has also identified other weaknesses of the WEP protocol (N. Borisov, I. Goldberg, and D. Wagner, “Intercepting Mobile Communications: The Insecurity of 802.11”, MOBICOM 2001, 2001).
The authentication scheme of IEEE 802.11 also has known problems that are related to the weaknesses in its encryption scheme. IEEE 802.11 APs provide two methods to protect against unauthorized accesses: Medium Access Control (MAC) address filtering and WEP-based shared-key authentication. A MAC address filter simply drops all data frames whose destination or source addresses are not listed in a pre-defined “allowed list”. However, because MAC addresses can easily be sniffed and forged by any attacker, the MAC address filter offers little protection against unauthorized network accesses. The shared-key authentication process involves both parties (named initiator and responder) encrypting the same challenge using WEP with the same shared-key but different IVs. Since the shared-key authentication algorithm authorizes network access to those who have the shared-key, it would be effective only if unauthorized parties cannot recover the shared-key. However, with WEP being breakable, the shared-key authentication becomes only an illusion.
Also known in the art is the IEEE's 802.11i (802.11i, IEEE 802.11 Task Group I, work in progress) standard, which is developed to replace the current WEP based security mechanism of the 802.11 WLAN. The IEEE's 802.1x (Port Based Network Access Control) standard (“Port-Based Network Access Control”, IEEE, 2001), which is used as a component of 802.11i, specifies an architectural framework that is designed to provide user authentication, network access control, and dynamic key management. Within the IEEE 802.1x framework, a system can use various specific authentication schemes and algorithms. The actual algorithm that is used to determine whether a user is authentic is left open and multiple algorithms are possible. One known popular algorithm is the Remote Authentication Dial In User Service (RADIUS) (IETF RFC 2965, June 2000).
In addition, the Extensible Authentication Protocol over LAN (EAPOL) and other variations of the Extensible Authentication Protocol (EAP), L. Blunk and J. Vollbrecht, “PPP Extensible Authentication Protocol (EAP)”, IETF RFC 2284, March, 1998) are known in the art due to their roles in the IEEE 802.1x and 802.11i protocols. EAP is built around the challenge-response communication paradigm that is common in network security solutions. Although originally designed as an authentication method for PPP connection, it can also be used for a wide range of LAN types such as Ethernet, token ring, or WLANs.
The IEEE 802.1x protocol is briefly explained. The IEEE 802.1x is a port-based, access control framework for wired or wireless networks that decides whether a client is authorized to use the network access service and then implements the decision. There are three types of entities in the IEEE 802.1x framework: supplicants, authenticators, and an authentication server. A supplicant is a client who wishes to use the network access service. An authenticator is a device which separates the supplicant from the rest of the network, i.e. an AP, and prevents unauthorized access. The authentication server is a backend server which makes the decision of granting or denying the supplicant's request. After the decision, the authenticator either blocks the supplicant's data traffic or lets it pass through.
IEEE 802.1x messages are transmitted using two versions of the EAP over two types of connections: 1) the link layer (LAN or WLAN) connections between the authenticators and supplicants and 2) the transport layer connections between the authenticators and the authentication server. For the first type of connection, IEEE 802.1x defines the Extensible Authentication Protocol over LAN (EAPOL). For the second type of connections, although the IEEE 802.1x does not define its own protocol, installations have been using a protocol based on the specifications defined by the “EAP over RADIUS” standard (C. Rigney, W. Willats, and P. Calhoun, “RADIUS Extensions”, IETF RFC2869, 2000). The Remote Access Dial-In User Services itself is defined in (C. Rigney, W. Willens, A. Rubens, and W. Simpson, “Remote Authentication Dial In User Service (RADIUS)”, IETF RFC2865, 2000).
A typical IEEE 802.1x authentication session starts when the client (supplicant) sends an EAPOL-Start message to an access point (authenticator) indicating its interest in using network access service. Upon receiving this message, the authenticator sends back an EAP-Request/Identity message. The supplicant must respond with an EAP-Response/Identity message. After receiving the supplicant's identity, the authenticator then needs to contact the authentication server by forwarding the supplicant's identity response to it. From this point on, the authentication message exchanges are between the supplicant and the authentication server. The details of the message exchanges depend on the actual authentication (referred to as Upper Layer Authentication or ULA) algorithm being used. The IEEE 802.1x supports a number of such ULA mechanisms such as the Transport Layer Security (TLS) (T. Dierks, and C. Allen, “The TLS Protocol Version 1.0”, IETF RFC2246, 1999) and the Kerberos V5 (J. Kohl, and C. Neuman, “The Kerberos Network Authentication Service (V5)”, IETF RFC1510, 1993). Although all ULA messages pass through the authenticator, the authenticator needs not understand any of them. At the end of the authentication sequence, the authentication server makes a decision of either granting or denying the supplicant's access request. The decision is sent to the supplicant in an EAP-Success or EAP-Failure message. When the authenticator is forwarding this final Success/Failure message to the supplicant, it too understands the message and hence executes the decision to either allow or block the supplicant's data traffic.
WPA′ method of using keys is now explained. Instead of using a single shared key for everything, WPA uses four 128-bit keys for protecting each pairwise communication: one pair of keys for protecting data encryption and data integrity and one pair of keys for protecting the communication between the two devices during their initial handshake. Collectively these four keys together are known as the Pairwise Transient Keys (PTK). Similarly each one-to-many group communication session is also protected by a Group Transient Key (GTK). The transient keys are changed for every data packet sent.
Despite the fact that so many keys are used, WPA only requires the configuration of one single key, the master key, for each pair of communicating devices or each group communication source. All other keys are derived from the master keys. Such a key organization is called a key hierarchy. In WPA, the pairwise master keys are a by-product of the authentication process as they are the session keys established by the RADIUS server at the end of the authentication procedure. Group master keys are separately selected by the group communication sources.
The PTKs are never exchanged between a pair of communicating nodes. Instead, they are computed independently by these two nodes. A four-way handshake is designed as part of TKIP to exchange the PTK computing parameters between a pair of nodes. The key generating parameters include such values that with extremely high confidence, the resulting transient key will be different for every time and every pair of nodes. At the end of this four-way handshake, both sides will have the same key generating parameters so they can generate the same PTK. Also proven during the handshake is that both sides know the same master key and therefore mutual authentication is achieved. After the PTKs are computed, GTKs are computed only by group communication sources and delivered to receivers via the already secured pairwise communications between the sources and receivers. GTKs may need to be re-computed and re-distributed from time to time due to group changes.
The data encryption keys of the PTKs and GTKs are then used by TKIP to generate a per-packet key, which is sent to an RC4 algorithm along with an IV to generate the key stream. Unlike in WEP where the shared key is used directly by RC4, TKIP performs per-packet key mixing and only the result is used by RC4. Hence the data encryption key of TKIP is much better protected. In addition the TKIP IVs are 48 bits long. With such a huge IV space, IV collision is not expected to occur and known weak keys can also be avoided. The IVs are also used by TKIP as data frame sequence numbers to prevent replay attacks.
The following is a description of 802.1x-based authentication and dynamic encryption. FIG. 1 shows the components involved in IEEE 802.1x authentication operations. In a WLAN 100 with IEEE 802.1x, a client (also known as a supplicant) 102 requests access service to an AP (or an authenticator) 104. The AP 104 opens an unauthorized port for the client 102, which only allows EAP messages to or from the supplicant (client) 102 to pass through. Through this unauthorized port, the supplicant 102 exchanges EAP messages with the authenticator 104 and the authentication server 106, which is a backend server executing the authentication algorithms. At the end of the authentication algorithm, the authentication server 106 returns an “accept” or “reject” instruction back to the authenticator 104. Upon receiving an “accept” message, the AP 104 opens the regular network access port for the client 102 to allow normal traffic for this client 102 to go through.
Also known in the art is the Wi-Fi Protected Access (WPA). WPA is a subset of the IEEE 802.11i standard, which only contains the authentication process and an encryption algorithm known as the Temporal Key Integrity Protocol (TKIP). Since WPA can be supported by most current WLAN hardware chipsets, it is considered the transition standard towards full IEEE 802.11i compliance, which requires new chipset and hardware design.
The WPA specification does not handle ad hoc links. Only its superset standard, IEEE 802.11i, contains any specifications for providing security to ad hoc links, and in this each ad hoc link is managed individually. The IEEE 802.1x type of authentication is not used, as ad hoc links are thought to be typically created in an infrastructureless network where there would rarely be a RADIUS server available. Two devices interested in communicating via an ad hoc link must have a “pre-shared” key. This key, typically configured manually, is used as the master key in the subsequent WPA transient key generation. The device with lower MAC address will act as the supplicant and initiate the 4-way WPA key material exchange handshake. After the handshake is completed, each end sends its own group key to the other end.
IEEE 802.1d MAC Bridge protocol (“Part 3: Media Access Control (MAC) Bridges”, IEEE, 1998 (IEEE 802.1d); “Part 3: Media Access Control (MAC) Bridges—Amendment 2: Rapid Reconfiguration”, IEEE, 2001 (IEEE 802.1w)) is known in the art.
IEEE 802.1d employs a spanning tree protocol, which is its method of forming a packet forwarding topology while preventing forwarding loops within a network of bridging devices. In an arbitrarily connected network, each bridge includes multiple ports. These ports are attached to a number of LAN segments. Among all bridges in a network, one bridge acts as the “root” of the spanning tree. It is the bridge with the highest priority bridge identifier (the priority identifier of a bridge is either derived from the unique ID of the bridge, which is typically the lowest MAC address among those of the bridge's ports, or configured by the network administrator).
In this protocol, each bridge uses each of its ports to report the following to its neighboring bridges: its own identity, the identity of the transmitting port, the identity of the bridge that the transmitting bridge believes to be the root, and the cost of the path from the transmitting port to the root bridge. Each bridge starts by assuming itself to be the root. If a bridge receives information that is “better” than what it currently has, it will re-compute its information based on the newly received information and then send out updated control messages to its neighboring bridges. What is considered “better information” includes information such as a bridge being a better root (with higher priority bridge identifier), a shorter path towards the root, lower cost routes, etc. Eventually through information propagation, all bridges learn the active spanning tree topology and configure their ports to forward data frames accordingly. On each bridge, the port that is the closest to the root is known as the “root port”. On each LAN segment, the bridge that can provide the shortest path towards the root is known as the “designated bridge” for the LAN segment.
Further known in the art are additional standard network protocols and schemes such as DHCP, NAT, ARP, reverse ARP and Proxy ARP.